#include <stdio.h>
#include "LinkTree.h"
#include <stdlib.h>
#include <string.h>
#define true 1
#define false 0

LTNode *CreateTreeNode(ElementType element)
{
    LTNode *newNode = (LTNode *)malloc(sizeof(LTNode));//使用malloc函数动态分配内存
    if (newNode == NULL)
    {
        printf("create malloc error!\n");
        return NULL;
    }
    newNode->data = element;
    newNode->firstChild = NULL;
    newNode->nextSibling = NULL;
    newNode->parent = NULL;
    return newNode;//LTNode *)是对返回指针的强制类型转换，将malloc的返回类型void *转换为LTNode *
}

void ConnectBranch(LTNode *parent, LTNode *child)
{
    if (parent == NULL || child == NULL)//空指针检查
    {
        return;
    }
    child->nextSibling = parent->firstChild;//将child插入到parent的子节点链表的开头位置
    parent->firstChild = child;//child成为parent的新的第一个子节点
    child->parent = parent;//建立父子关系
}

void DisConnectBranch(LTNode *parent, LTNode *child)
{
    if (parent == NULL || child == NULL || parent->firstChild == NULL)
    {
        return;
    }//用于检查parent、child是否为NULL，以及parent是否具有子节点。

    LTNode *travelPoint = parent->firstChild;
    if (travelPoint == child)//用于判断child是否是parent的第一个子节点。
    {
        parent->firstChild = child->nextSibling;//将parent的firstChild指针指向child节点的下一个兄弟节点，即跳过了child节点。
        child->parent = NULL;
        child->nextSibling = NULL;
        return;//断开连接后，函数直接返回，结束执行。
    }

    while (travelPoint->nextSibling != NULL)
    {
        if (travelPoint->nextSibling == child)//判断travelPoint的下一个兄弟节点是否是child节点。
        {
            travelPoint->nextSibling = child->nextSibling;
            child->parent = NULL;
            child->nextSibling = NULL;
            return;//函数直接返回，结束执行。
        }
        travelPoint = travelPoint->nextSibling;
    }
}

void FreeNode(LTNode *treeNode)//一个递归函数FreeNode的实现，用于释放LinkTreeNode节点及其子节点占用的内存
{
    if (treeNode == NULL)
        return;//如果传入的treeNode为空指针，则直接返回，不进行任何操作

    FreeNode(treeNode->firstChild);
    FreeNode(treeNode->nextSibling);//释放treeNode的子节点链表和兄弟节点链表的内存
    free(treeNode);//函数释放treeNode节点本身占用的内存。


    // LTNode *travelPoint = treeNode->firstChild;
    // while (travelPoint != NULL)
    // {
    //     LTNode *nextNode = travelPoint->nextSibling;
    //     FreeNode(travelPoint);
    //     travelPoint = nextNode;
    // }
    // free(treeNode)
}

int InitLTree(LTree *tree)//初始化一个 LTree 结构
{
    struct UniversalType typedata = {NULL,-1};//被赋值为 -1 的整数值是用来表示初始化失败的标志。
    tree->root = CreateTreeNode(typedata);
    if (tree->root == NULL)
    {
        return false;
    }
    else
    {
        return true;
    }
}

void FreeTree(LTree *tree)
{
    FreeNode(tree->root);//调用 FreeNode 函数来递归地释放二叉树的每个节点的内存资源。
    tree->root = NULL;
}

int GetNodeHeight(LTNode *treeNode)//用于计算二叉树节点的高度。
{
    if (treeNode == NULL)
        return 0;//如果是 NULL，说明当前节点为空，表示到达了二叉树的叶子节点或空节点，所以返回高度为 0。
    int height = 0;//在每一层递归调用的开始，将当前层的高度初始化为 0。
    LTNode *travelPoint = treeNode->firstChild;//遍历当前节点的子节点。
    while (travelPoint != NULL)
    {
        int childHeight = GetNodeHeight(travelPoint);//对于当前子节点，递归调用 GetNodeHeight 函数，计算子节点的高度。
        height = height > childHeight ? height : childHeight;//比较当前节点的高度 height 和子节点的高度 childHeight，将较大值赋给 height。
        travelPoint = travelPoint->nextSibling;//移动到下一个兄弟节点，以便在下一次循环中遍历兄弟节点。
    }
    return height + 1;//完成对所有子节点的遍历后，返回当前节点的高度，即最大子节点高度加1。
}
int GetTreeHeight(LTree *tree)
{
    return GetNodeHeight(tree->root);//在 GetTreeHeight 函数中，它调用了 GetNodeHeight 函数并传入二叉树的根节点 tree->root 作为参数。
}

LTNode *FindNode(LTNode *node,ElementType element, int(*func)(ElementType,ElementType))
{//用于在一棵树中查找具有特定属性的节点。
    if (node == NULL)
        return NULL;

    // if (strcmp(node->data, element) == 0)
    // {
    //     return node;
    // }
    if(func != NULL && func(node->data,element)== true)//通过调用该函数判断当前节点 node 是否具有特定属性
    {
        return node;
    }

    LTNode *childNode = node->firstChild;//初始化一个指针 childNode，用于遍历当前节点的子节点。
    LTNode *targetNode = NULL;//初始化一个指针 targetNode，用于记录找到的目标节点。
     while (childNode != NULL)
     {
         targetNode = FindNode(childNode,element,func);//对于当前子节点，递归调用 FindNode 函数，在该子节点为根的子树中查找符合要求的节点
         if (targetNode != NULL)
         {
             return targetNode;
         }
         childNode = childNode->nextSibling;//移动到下一个兄弟节点，以便在下一次循环中遍历兄弟节点。
     }
     return targetNode;
    // if (targetNode = FindNode(node->firstChild, element) != NULL)
    // {
    //     return targetNode;
    // }
    // if (targetNode = FindNode(node->nextSibling, element) != NULL)
    // {
    //     return targetNode;
    // }
    // return targetNode;
}
LTNode *FindTreeNode(LTree *node,ElementType element, int(*func)(ElementType,ElementType))
{
    return FindNode(node->root,element,func);//调用了 FindNode 函数并传入树的根节点 node->root
}

void TravelTreeNode(LTNode *node, int deepth,void(*func)(ElementType))//用于遍历树的节点并执行特定的操作
{
    if (node == NULL)
        return;
    if (func != NULL)
    {
        func(node->data);
    }
    
    // for (int i = 0; i < deepth; i++)
    //     printf("  ");
    // if (node->parent != NULL)
    //     printf("|__");
    // printf("%s \n", node->data);
    // LTNode *travelPoint = node->firstChild;
    // while (travelPoint != NULL)
    // {
    //     TravelTreeNode(travelPoint);
    //     travelPoint = travelPoint->nextSibling;
    // }
    TravelTreeNode(node->firstChild, deepth + 1,func);
    TravelTreeNode(node->nextSibling, deepth,func);
}

void Travel(LTree *tree,void(*func)(ElementType))
{
    TravelTreeNode(tree->root, 0,func);
}
